package vn.edu.hut.soict.translate.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

import vn.edu.hut.soict.automaton.State;
import vn.edu.hut.soict.automaton.Transition;
import vn.edu.hut.soict.translate.utils.SemanticDistance;
import vn.edu.hut.soict.translate.wordgraph.Word;
import vn.edu.hut.soict.translate.wordgraph.WordGraph;

public class SearchState implements Comparable<SearchState> {
	private List<List<Record>> paths;
	private State<Word> node;
	private Word[] input;
	private int inputIndex;
	private Operator trans;

	private double cost;
	private double evaluateCost;

	private int cInput;
	private int fInput;
	private int cGraph;
	private int fGraph;

	private SearchState() {
		paths = new ArrayList<List<Record>>();
		trans = Operator.NIL;
		cost = -1;
		evaluateCost = -1;
		inputIndex = 0;
	}

	public SearchState(State<Word> node, Word[] input) {
		this();
		this.node = node;
		this.input = input;
		trans = Operator.EXACT_MATCH;
		paths.add(new ArrayList<Record>());
		cInput = 0;
		fInput = 0;
		for (int i = 0; i < input.length; i++) {
			if (input[i].isContentWord()) {
				cInput++;
			}
			else {
				fInput++;
			}
		}
		cGraph = wordGraph().getContentWordCount();
		fGraph = wordGraph().getFunctionWordCount();
	}

	public boolean isGoalState() {
		return node.isFinal() && inputIsEmpty();
	}

	@Override
	public int compareTo(SearchState s) {
		return Double.compare(getEvaluateCost(), s.getEvaluateCost());
	}

	public List<List<Record>> getPaths() {
		return paths;
	}

	public State<Word> getNode() {
		return node;
	}

	public Operator getTrans() {
		return trans;
	}

	public double getCost() {
		if (cost >= 0) {
			return cost;
		}
		if (paths.size() == 0) {
			cost = 0;
		}
		else {
			double sum = 0;
			for (Record record : paths.get(0)) {
				sum += record.getCost();
			}
			cost = sum;
		}
		return cost;
	}

	public double getEvaluateCost() {
		if (evaluateCost >= 0) {
			return evaluateCost;
		}
		evaluateCost = getCost() + calculateHeuristicCost();
		return evaluateCost;
	}

	public Word headOfInput() {
		if (inputIndex < input.length) {
			return input[inputIndex];
		}
		else {
			return null;
		}
	}

	public void removeInputHead() {
		if (inputIndex < input.length) {
			if (input[inputIndex].isContentWord()) {
				cInput--;
			}
			else {
				fInput--;
			}
			inputIndex++;
		}
		else {
			System.err.println("Input is empty");
		}
	}

	public boolean inputIsEmpty() {
		return (inputIndex == input.length);
	}

	@Override
	protected SearchState clone() {
		SearchState s = new SearchState();
		for (List<Record> path : paths) {
			List<Record> clonePath = new ArrayList<Record>();
			for (Record record : path) {
				clonePath.add(record.clone());
			}
			s.paths.add(clonePath);
		}
		s.node = node;
		s.input = input;
		s.inputIndex = inputIndex;
		s.trans = trans;
		s.cInput = cInput;
		s.fInput = fInput;
		s.cGraph = cGraph;
		s.fGraph = fGraph;
		return s;
	}

	public List<SearchState> getSuccessors() {
		List<SearchState> successors = new ArrayList<SearchState>();
		if (checkTCondition()) {
			successors.add(createTSuccessor());
		}
		if (checkICondition()) {
			successors.add(createISuccessor());
		}
		for (Transition<Word> t : node.getNextTransitions()) {
			if (checkECondition(t)) {
				successors.add(createESuccessor(t));
			}
			if (checkSCondition(t)) {
				successors.add(createSSuccessor(t));
			}
			if (checkDCondition(t)) {
				successors.add(createDSuccessor(t));
			}
		}
		return successors;
	}

	private boolean checkTCondition() {
		return trans == Operator.EXACT_MATCH || trans == Operator.SUBSTITUTION;
	}

	private boolean checkECondition(Transition<Word> t) {
		return trans == Operator.EXACT_MATCH && !inputIsEmpty() && t.getSymbol().equals(headOfInput());
	}

	private boolean checkSCondition(Transition<Word> t) {
		return trans == Operator.SUBSTITUTION && !inputIsEmpty() && !t.getSymbol().equals(headOfInput()) && t.getSymbol().isContentWord() && headOfInput().isContentWord() && t.getSymbol().samePartOfSpeech(headOfInput()) && SemanticDistance.calculate(t.getSymbol().getText(), headOfInput().getText()) < 1;
	}

	private boolean checkICondition() {
		return trans == Operator.NIL && !inputIsEmpty();
	}

	private boolean checkDCondition(Transition<Word> t) {
		return trans == Operator.NIL && hasAnAppropiratePath();
	}

	// Return true if state s includes a path whose last record is not an
	// I-record.
	private boolean hasAnAppropiratePath() {
		for (List<Record> path : paths) {
			if (path.size() > 0 && path.get(path.size() - 1).getOperator() != Operator.INSERTION) {
				return true;
			}
			else if (path.size() == 0) {
				return true;
			}
		}
		return false;
	}

	private SearchState createTSuccessor() {
		SearchState s = clone();
		if (trans == Operator.EXACT_MATCH) {
			s.trans = s.select_S_NIL();
		}
		else if (trans == Operator.SUBSTITUTION) {
			s.trans = Operator.NIL;
		}
		else {
			System.err.println("Conditions are not satified.");
			return null;
		}
		return s;
	}

	private SearchState createESuccessor(Transition<Word> t) {
		SearchState s = clone();
		for (List<Record> path : s.paths) {
			path.add(new Record(Operator.EXACT_MATCH, headOfInput()));
		}
		if (headOfInput().isContentWord()) {
			s.cGraph--;
		}
		else {
			s.fGraph--;
		}
		s.node = t.getTarget();
		s.removeInputHead();
		s.trans = s.select_E_S_NIL();
		return s;
	}

	private SearchState createSSuccessor(Transition<Word> t) {
		SearchState s = clone();
		for (List<Record> path : s.paths) {
			path.add(new Record(Operator.SUBSTITUTION, t.getSymbol(), headOfInput()));
		}
		if (headOfInput().isContentWord()) {
			s.cGraph--;
		}
		else {
			s.fGraph--;
		}
		s.node = t.getTarget();
		s.removeInputHead();
		s.trans = s.select_E_S_NIL();
		return s;
	}

	private SearchState createISuccessor() {
		SearchState s = clone();
		for (List<Record> path : s.paths) {
			path.add(new Record(Operator.INSERTION, headOfInput()));
		}
		s.removeInputHead();
		s.trans = s.select_E_S_NIL();
		return s;
	}

	private SearchState createDSuccessor(Transition<Word> t) {
		SearchState s = clone();
		Iterator<List<Record>> iterator = s.paths.iterator();
		while (iterator.hasNext()) {
			List<Record> path = iterator.next();
			if (path.size() > 0 && path.get(path.size() - 1).getOperator() == Operator.INSERTION) {
				iterator.remove();
			}
		}
		for (List<Record> path : s.paths) {
			path.add(new Record(Operator.DELETION, t.getSymbol()));
		}
		if (t.getSymbol().isContentWord()) {
			s.cGraph--;
		}
		else {
			s.fGraph--;
		}
		s.node = t.getTarget();
		s.trans = s.select_E_S_NIL();
		return s;
	}

	private Operator select_S_NIL() {
		if (!inputIsEmpty() && headOfInput().isContentWord()) {
			for (Transition<Word> transition : node.getNextTransitions()) {
				Word label = transition.getSymbol();
				if (label.samePartOfSpeech(headOfInput()) && !label.isIdentical(headOfInput())) {
					return Operator.SUBSTITUTION;
				}
			}
		}
		return Operator.NIL;
	}

	private Operator select_E_S_NIL() {
		for (Transition<Word> transition : node.getNextTransitions()) {
			if (transition.getSymbol().isIdentical(headOfInput())) {
				return Operator.EXACT_MATCH;
			}
		}
		return select_S_NIL();
	}

	private double calculateHeuristicCost() {
		if (isGoalState()) {
			return 0;
		}
		switch (trans) {
			case EXACT_MATCH:
				return heuristicCost(Operator.EXACT_MATCH);
			case SUBSTITUTION:
				return Math.min(heuristicCost(Operator.SUBSTITUTION), Math.min(heuristicCost(Operator.INSERTION), heuristicCost(Operator.DELETION)));
			case NIL:
				return Math.min(heuristicCost(Operator.INSERTION), heuristicCost(Operator.DELETION));
			default:
				throw new IllegalArgumentException("Invalid type of trans.");
		}
	}

	private double heuristicCost(Operator operator) {
		switch (operator) {
			case EXACT_MATCH:
				return Math.abs(cInput - cGraph) + Math.abs(fInput - fGraph);
			case SUBSTITUTION:
				return Math.abs(cInput - cGraph) + Math.abs(fInput - fGraph) + Record.MIN_COST_OF_S_RECORD;
			case INSERTION:
				if (!inputIsEmpty()) {
					if (headOfInput().isContentWord()) {
						return Math.abs(cInput - 1 - cGraph) + Math.abs(fInput - fGraph) + 1;
					}
					else {
						return Math.abs(cInput - cGraph) + Math.abs(fInput - 1 - fGraph) + 1;
					}
				}
				else {
					return Double.MAX_VALUE;
				}
			case DELETION:
				boolean cCondition = true;
				boolean fCondition = true;
				int Hc = Math.abs(cInput - cGraph + 1) + Math.abs(fInput - fGraph);
				int Hf = Math.abs(cInput - cGraph) + Math.abs(fInput - fGraph + 1);
				for (Transition<Word> transition : node.getNextTransitions()) {
					if (!transition.getSymbol().isContentWord()) {
						cCondition = false;
						if (!fCondition) {
							break;
						}
					}
					else {
						fCondition = false;
						if (!cCondition) {
							break;
						}
					}
				}
				if (cCondition) {
					return Hc + 1;
				}
				else if (fCondition) {
					return Hf + 1;
				}
				else {
					return Math.min(Hc, Hf);
				}
			default:
				throw new IllegalArgumentException("Invalid type of operator.");
		}
	}

	@Override
	public String toString() {
		return "SearchState(node = " + node.toString() + "; inputIndex = " + inputIndex + "; trans = " + trans + "; paths = " + paths.toString() + ")";
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + cInput;
		result = prime * result + fInput;
		result = prime * result + Arrays.hashCode(input);
		result = prime * result + inputIndex;
		result = prime * result + ((node == null) ? 0 : node.hashCode());
		result = prime * result + ((trans == null) ? 0 : trans.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) {
			return true;
		}
		if (obj == null) {
			return false;
		}
		if (getClass() != obj.getClass()) {
			return false;
		}
		SearchState other = (SearchState) obj;
		if (cInput != other.cInput || fInput != other.fInput) {
			return false;
		}
		if (!Arrays.equals(input, other.input) || inputIndex != other.inputIndex) {
			return false;
		}
		if (node != other.node || trans != other.trans) {
			return false;
		}
		return true;
	}

	private WordGraph wordGraph() {
		return (WordGraph) node.getAutomaton();
	}

	public void removeInsufficientPath(double threshold) {
		WordGraph wordGraph = wordGraph();
		int candidateLength = wordGraph.getContentWordCount() + wordGraph.getFunctionWordCount();
		double insertionMax = 2 * threshold * candidateLength / (1 - threshold);
		double deletionMax = 2 * threshold * candidateLength / (1 + threshold);

		Iterator<List<Record>> iterator = paths.iterator();
		while (iterator.hasNext()) {
			List<Record> path = iterator.next();
			int iCount = 0;
			int dCount = 0;

			for (Record record : path) {
				switch (record.getOperator()) {
					case INSERTION:
						iCount++;
						break;
					case DELETION:
						dCount++;
						break;
				}
			}

			if (iCount > insertionMax || dCount > deletionMax) {
				iterator.remove();
			}
		}
	}
}